代写 algorithm COMP90038  Algorithms and Complexity

COMP90038  Algorithms and Complexity
Lecture 4: Analysis of Algorithms (with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray

2
Last Time: Time Complexity
Measure input size by natural number n Measure execution time as number of basic
• •
operations performed
Time complexity t(n) for an algorithm: number of
•
basic operations as a function of n
•
•
How to compare different t(n) ? Asymptotic growth rate
O(g(n)), Ω(g(n)), Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•

2
Last Time: Time Complexity
Measure input size by natural number n Measure execution time as number of basic
How to compare different t(n) ? Asymptotic growth rate
O(g(n)), Ω(g(n)), Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• •
•
•
operations performed
Time complexity t(n) for an algorithm: number of
•
basic operations as a function of n
•

Last Time: Time Complexity
Measure input size by natural number n Measure execution time as number of basic
• •
operations performed
Time complexity t(n) for an algorithm: number of
•
basic operations as a function of n
•
•
How to compare different t(n) ? Asymptotic growth rate
O(g(n)), Ω(g(n)), Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
2
•

Last Time: Time Complexity
Measure input size by natural number n Measure execution time as number of basic
How to compare different t(n) ? Asymptotic growth rate
O(g(n)), Ω(g(n)), Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• •
operations performed
Time complexity t(n) for an algorithm: number of
•
basic operations as a function of n
•
•
2
•

Establishing Growth Rate
In the last lecture we proved t(n) ∈ O(g(n)) for some
cases of t and g, using the definition of O directly:    
n >n0 ⇒ t(n) < c ·g(n) for some c and n0. A more common approach uses  • • f(n) { 0 f grows asymptotically slower than g lim g(n) =   c f and g have same order of growth • n→∞ ∞ f grows asymptotically faster than g 3 • Use this to show that 1000n ∈ O(n2) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n ∈ O(n2) lim n→∞ 1000n n2 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n ∈ O(n2) lim n→∞ 1000n n2 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n ∈ O(n2) lim n→∞ 1000n n2 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n ∈ O(n2) lim 1000n n2 1000 = n→∞ lim n 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License n→∞ 1000n ∈ O(n2) lim 1000n n2 1000 = =0 n n→∞ lim 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License n→∞ 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n ∈ O(n2) lim 1000n n2 1000 = =0 n n→∞ lim n→∞ So 1000n grows asymptotically slower than n2 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n ∈ O(n2) lim 1000n n2 1000 = =0 n n→∞ lim n→∞ So 1000n grows asymptotically slower than n2 Thus 1000n ∈ O(n2) O, Ω, Θ What this tells us about how f(n) relates to lim f(n) g(n) { 0 = c ∞ f grows asymptotically slower than g f and g have same order of growth f grows asymptotically faster than g • n→∞ O(g(n)), Ω(g(n)) and Θ(g(n)) 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ What this tells us about how f(n) relates to lim f(n) g(n) { 0 = c ∞ f grows asymptotically slower than g f and g have same order of growth f grows asymptotically faster than g • n→∞ O(g(n)), Ω(g(n)) and Θ(g(n)) 5 f(n) ∈ O(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ What this tells us about how f(n) relates to O(g(n)), Ω(g(n)) and Θ(g(n)) lim f(n) g(n) { 0 = c ∞ f(n) ∈ O(g(n)) f grows asymptotically slower than g f and g have same order of growth f grows asymptotically faster than g • n→∞ 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ What this tells us about how f(n) relates to lim f(n) g(n) { 0 = c ∞ f(n) ∈ O(g(n)) f grows asymptotically slower than g f and g have same order of growth f grows asymptotically faster than g • n→∞ O(g(n)), Ω(g(n)) and Θ(g(n)) 5 f(n) ∈ Ω(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ What this tells us about how f(n) relates to lim f(n) g(n) { 0 = c ∞ f(n) ∈ O(g(n)) f grows asymptotically slower than g f and g have same order of growth f grows asymptotically faster than g • n→∞ f(n) ∈ Ω(g(n)) O(g(n)), Ω(g(n)) and Θ(g(n)) 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ What this tells us about how f(n) relates to lim f(n) g(n) { 0 = c ∞ f(n) ∈ O(g(n)) f grows asymptotically slower than g f and g have same order of growth f grows asymptotically faster than g • n→∞ f(n) ∈ Ω(g(n)) O(g(n)), Ω(g(n)) and Θ(g(n)) 5 f(n) ∈ Θ(g(n)) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ What this tells us about how f(n) relates to f(n) n→∞ g(n) { 0 = c ∞ f(n) ∈ O(g(n)) f grows asymptotically slower than g f and g have same order of growth f(n)∈Θ(g(n)) f grows asymptotically faster than g f(n) ∈ Ω(g(n)) O(g(n)), Ω(g(n)) and Θ(g(n)) • lim 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) where t’ and g’ are the derivatives of t and g 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) where t’ and g’ are the derivatives of t and g n 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • For example, show that log2 n grows slower than        L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) • where t’ and g’ are the derivatives of t and g For example, show that log2 n grows slower than    logn  lim 2  n→∞ n n 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) • where t’ and g’ are the derivatives of t and g For example, show that log2 n grows slower than   n→∞ n n→∞ 2n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License n   log n (loge2)1  lim 2 =lim 1 n 6 L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) where t’ and g’ are the derivatives of t and g For example, show that log2 n grows slower than    logn (loge2)1 ( 1 )   lim 2 =lim n =lim (loge2) ⋅2 n  n→∞ n n→∞ 1 n→∞ n 2n • n 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) • n where t’ and g’ are the derivatives of t and g For example, show that log2 n grows slower than    logn (loge2)1 ( 1 )   lim 2 =lim n =lim (loge2) ⋅2 n  n→∞ n n→∞ 1 n→∞ n 2n =2loge2lim n 6 n→∞ n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) where t’ and g’ are the derivatives of t and g For example, show that log2 n grows slower than    logn (loge2)1 ( 1 )   lim 2 =lim n =lim (loge2) ⋅2 n  n→∞ n n→∞ 1 n→∞ n • n 2n =2loge2 lim n =2loge2 lim 1 n→∞ n n→∞ Copyright University of Melbourne 2016, provided under Creative Commons Attribution License n 6 L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) • n where t’ and g’ are the derivatives of t and g For example, show that log2 n grows slower than    logn (loge2)1 ( 1 )   lim 2 =lim n =lim (loge2) ⋅2 n  n→∞ n n→∞ 1 n→∞ n 2n =2loge2lim n =2loge2lim 1 =0 6 n→∞ n n→∞ n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array A: max: 23 0123456 (where n is length of the array) 23 12 42 6 69 18 3 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array A: max: 23 0123456 (where n is length of the array) 23 12 42 6 69 18 3 Example: Finding Largest Element in an Array (where n is length of the array) 23 12 42 6 69 18 3 A: max: 23 0123456 A[i] 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array (where n is length of the array) 23 12 42 6 69 18 3 A: max: 23 0123456 A[i] 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array (where n is length of the array) 23 12 42 6 69 18 3 A: max: 2432 0123456 A[i] 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array (where n is length of the array) 23 12 42 6 69 18 3 A: max: 2432 0123456 A[i] 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array (where n is length of the array) 23 12 42 6 69 18 3 A: max: 2432 0123456 A[i] 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array (where n is length of the array) 23 12 42 6 69 18 3 A: max: 246293 0123456 A[i] 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array (where n is length of the array) 23 12 42 6 69 18 3 A: max: 246293 0123456 A[i] 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array (where n is length of the array) 23 12 42 6 69 18 3 A: max: 246293 0123456 A[i] 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array (where n is length of the array) 8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License C(n) = Example: Finding Largest Element in an Array 8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License C(n) = (where n is length of the array) Size of input, n: length of the array Example: Finding Largest Element in an Array (where n is length of the array) Size of input, n: length of the array Basic operation: comparison “A[i] > max”
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =

Example:
Finding Largest Element in an Array
(where n is length of the array)
Size of input, n: length of the array
Basic operation: comparison “A[i] > max” Count the number of basic operations executed
for an array of size n: C(n) =
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

8
Example:
Finding Largest Element in an Array
(where n is length of the array)
Size of input, n: length of the array
Basic operation: comparison “A[i] > max”
Count the number of basic operations executed for an array of size n:
n−1
C(n) = ∑ 1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
i=1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
23
12
42
6
69
18
3
0123456
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
23
12
42
6
69
18
3
0123456
A[i]
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
23
12
42
6
69
18
3
0123456
A[i]
min: 0
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
23
12
42
6
69
18
3
0123456
A[i] A[j]
min: 0
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
23
12
42
6
69
18
3
0123456
A[i] A[j]
min: 01
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
23
12
42
6
69
18
3
0123456
A[i] A[j]
min: 301
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
23
12
42
6
69
18
3
0123456
A[i] A[j]
min: 6310
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i]
min: 036
10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i]
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i]
min: 1
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i] A[j]
min: 1
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i] A[j]
min: 13
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
3
6
42
12
69
18
23
0123456
A[i]
min: 03
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Input size n: length of the array
Basic operation: comparison A[j] < A[min] Example: Selection Sort C(n) = 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Input size n: length of the array Basic operation: comparison A[j] < A[min] Example: Selection Sort n−2 n−1 C(n) =∑ ∑ 1 i=0 j=i+1 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Input size n: length of the array Basic operation: comparison A[j] < A[min] Example: Selection Sort Basic operation: comparison A[j] < A[min] n−2 n−1 n−2 C(n) =∑ ∑ 1 = ∑ (n − 1 − i) i=0 j=i+1 i=0 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Input size n: length of the array Example: Selection Sort Basic operation: comparison A[j] < A[min] n−2 n−1 n−2 n−2 n−2 C(n) =∑ ∑ 1 = ∑ (n − 1 − i) = ∑ (n − 1) − ∑ i i=0 j=i+1 i=0 i=0 i=0 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Input size n: length of the array Example: Selection Sort Basic operation: comparison A[j] < A[min] n−2 n−1 n−2 n−2 n−2 C(n) =∑ ∑ 1 = ∑ (n − 1 − i) = ∑ (n − 1) − ∑ i i=0 j=i+1 = (n − 1)2 − i=0 i=0 i=0 (n−2)(n−1) 2 Input size n: length of the array 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Selection Sort Basic operation: comparison A[j] < A[min] n−2 n−1 n−2 n−2 n−2 C(n) =∑ ∑ 1 = ∑ (n − 1 − i) = ∑ (n − 1) − ∑ i i=0 j=i+1 i=0 i=0 i=0 =(n−1)2−(n−2)(n−1) =n(n−1)∈Θ(n2) 22 Input size n: length of the array 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication 57 82 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 57 82 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 0 57 82 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 0 57820 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 0 k: 0 57820 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 0 k: 0 57 82 400 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 0 k:10 57 82 400 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 0 k:10 57 82 1403 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 1 57 82 103 34 96 ABC 15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 1 57 82 1030 34 96 ABC 15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 1 k: 0 57 82 1030 34 96 ABC 15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 1 k: 0 57 82 10310 34 96 ABC 15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 1 k:10 57 82 10310 34 96 ABC 15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 1 k:10 57 82 10351020 34 96 ABC 15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 = ∑ ∑ ((n − 1) − 0 + 1) i=0 j=0 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n i=0 j=0 i=0 j=0 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n =∑∑(n⋅1) i=0 j=0 i=0 j=0 i=0 j=0 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n =∑∑(n⋅1) i=0 j=0 i=0 j=0 i=0 j=0 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n =∑∑(n⋅1) i=0 j=0 i=0 j=0 i=0 j=0 n−1 n−1 =∑ n⋅∑1 i=0 j=0 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n =∑∑(n⋅1) i=0 j=0 n−1 n−1 i=0 j=0 i=0 j=0 n−1 2 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License =∑ n⋅∑1 =∑n i=0 j=0 i=0 Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n =∑∑(n⋅1) i=0 j=0 n−1 n−1 i=0 j=0 i=0 j=0 n−1 2 17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License =∑ n⋅∑1 =∑n i=0 j=0 = n3 i=0 Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n =∑∑(n⋅1) i=0 j=0 n−1 n−1 i=0 j=0 i=0 j=0 17 ∈ Θ(n3) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License n−1 2 =∑ n⋅∑1 =∑n i=0 j=0 = n3 i=0 Analysing Recursive  Algorithms 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms F(5) 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms F(5) =F(4)⋅5 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms F(5) =F(4)⋅5 = (F(3) ⋅ 4) ⋅ 5 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms F(5) =F(4)⋅5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms F(5) =F(4)⋅5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms F(5) =F(4)⋅5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms F(5) =F(4)⋅5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((1 ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms F(5) =F(4)⋅5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((1 ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = 5! 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive  Algorithms 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) M(0) = 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) M(0)= 0 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) M(0)= 0 M(n) = 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) M(0)= 0 M(n)= M(n−1)+1 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) M(0)= 0 M(n)= M(n−1)+1 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) M(0)= 0 M(n)= M(n−1)+1 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) M(0)= 0 M(n)= M(n−1)+1 Need to express M(n) in closed form (i.e. non-recursively) 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Analysing Recursive  Algorithms We express the cost recursively (as a recurrence relation) M(0)= 0 M(n)= M(n−1)+1 Need to express M(n) in closed form (i.e. non-recursively) Try: “telescoping” aka “backward substitution” 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 M(0) = 0 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 M(0) = 0 What is M(n-1) ? 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 M(0) = 0 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 M(0) = 0 What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 M(0) = 0 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License What is M(n-1) ? M(n) = M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 M(0) = 0 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License What is M(n-1) ? M(n)= (M(n−2)+1)+1 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License ... Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License = (M(n − 3) + 1) + 2 = M(n − 3) + 3 ... = M(n − n) + n Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 20 = M(0) + n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License = (M(n − 3) + 1) + 2 = M(n − 3) + 3 ... = M(n − n) + n Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 20 =n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License = (M(n − 3) + 1) + 2 = M(n − 3) + 3 ... = M(n − n) + n = M(0) + n Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 Closed form: 20 =n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License = (M(n − 3) + 1) + 2 = M(n − 3) + 3 ... = M(n − n) + n = M(0) + n 20 Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = M(n − 2) + 1 Closed form: = (M(n − 3) + 1) + 2 = M(n − 3) + 3 M(n) = n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License ... = M(n − n) + n = M(0) + n =n Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 = M(n − 2) + 1 Closed form: 20 =n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License ... = M(n − n) + n M(n) = n Complexity: = M(0) + n Telescoping  (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 = M(n − 2) + 1 Closed form: 20 ... = M(n − n) + n M(n) = n Complexity: = M(0) + n M(n) ∈ Θ(n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License =n Example:  Binary Search in Sorted Array 4 9 13 22 41 83 96 A: 0123456 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array 4 9 13 22 41 83 96 A: 0123456 BinSearch(A,0,6,41) 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: 0123456 BinSearch(A,0,6,41) 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License lo: 0 4 9 13 22 41 83 96 Example:  Binary Search in Sorted Array A: 0123456 BinSearch(A,0,6,41) 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License lo: 0 hi: 6 4 9 13 22 41 83 96 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,0,6,41) 0123456 lo: 0 hi: 6 key: 41 4 9 13 22 41 83 96 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,0,6,41) 0123456 lo: 0 hi: 6 key: 41 mid: 3 4 9 13 22 41 83 96 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,0,6,41) BinSearch(A,4,6,41) 0123456 lo: 0 hi: 6 key: 41 mid: 3 4 9 13 22 41 83 96 Example:  Binary Search in Sorted Array 4 9 13 22 41 83 96 A: 0123456 BinSearch(A,4,6,41) 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array 4 9 13 22 41 83 96 A: 0123456 BinSearch(A,4,6,41) 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: 0123456 BinSearch(A,4,6,41) 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License lo: 4 4 9 13 22 41 83 96 Example:  Binary Search in Sorted Array A: 0123456 BinSearch(A,4,6,41) 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License lo: 4 hi: 6 4 9 13 22 41 83 96 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,4,6,41) 0123456 lo: 4 hi: 6 key: 41 4 9 13 22 41 83 96 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,4,6,41) 0123456 lo: 4 hi: 6 key: 41 mid: 5 4 9 13 22 41 83 96 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,4,6,41) BinSearch(A,4,4,41) 0123456 lo: 4 hi: 6 key: 41 mid: 5 4 9 13 22 41 83 96 Example:  Binary Search in Sorted Array 4 9 13 22 41 83 96 A: 0123456 BinSearch(A,4,4,41) 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array 4 9 13 22 41 83 96 A: 0123456 BinSearch(A,4,4,41) 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: 0123456 BinSearch(A,4,4,41) 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License lo: 4 4 9 13 22 41 83 96 Example:  Binary Search in Sorted Array A: 0123456 BinSearch(A,4,4,41) 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License lo: 4 hi: 4 4 9 13 22 41 83 96 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,4,4,41) 0123456 lo: 4 hi: 4 key: 41 4 9 13 22 41 83 96 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,4,4,41) 0123456 lo: 4 hi: 4 key: 41 mid: 4 4 9 13 22 41 83 96 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array A: BinSearch(A,4,4,41) returns 4 0123456 lo: 4 hi: 4 key: 41 mid: 4 4 9 13 22 41 83 96 Example:  Binary Search in Sorted Array Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array Basic operation: key comparison A[mid] = key Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(0) = Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(0) = 0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example:  Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(n) = C(n/2) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License C(0) = 0 Example:  Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(n) = C(n/2) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License C(0) = 0 Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 ... Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 ... = C(n/n) + log2 n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 ... = C(n/n) + log2 n = (C(0) + 1) + log2 n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 ... = C(n/n) + log2 n = (C(0) + 1) + log2 n = 1 + log2 n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 ... C(n) ∈ Θ(log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License = C(n/n) + log2 n = (C(0) + 1) + log2 n = 1 + log2 n Logarithmic Functions  Have Same Rate of Growth In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) 26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions  Have Same Rate of Growth In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim logan = lim (loga b)(logb n) = (loga b) lim 1 = loga b n→∞ logbn n→∞ logb n n→∞ 26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions  Have Same Rate of Growth In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim logan = lim (loga b)(logb n) = (loga b) lim 1 = loga b n→∞ logbn n→∞ logb n n→∞ So, e.g.: 26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Logarithmic Functions  Have Same Rate of Growth In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since 26 loga x = (loga b)(logb x) lim logan = lim (loga b)(logb n) = (loga b) lim 1 = loga b n→∞ logbn n→∞ logb n n→∞ O(logan) = O(logbn) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License So, e.g.: Logarithmic Functions  Have Same Rate of Growth In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since 26 loga x = (loga b)(logb x) lim logan = lim (loga b)(logb n) = (loga b) lim 1 = loga b n→∞ logbn n→∞ logb n n→∞ O(logan) = O(logbn) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License So, e.g.: Also, since Logarithmic Functions  Have Same Rate of Growth In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since 26 loga x = (loga b)(logb x) lim logan = lim (loga b)(logb n) = (loga b) lim 1 = loga b n→∞ logbn n→∞ logb n n→∞ O(logan) = O(logbn) Also, since log nc = c ⋅ log n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License So, e.g.: Logarithmic Functions  Have Same Rate of Growth In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim logan = lim (loga b)(logb n) = (loga b) lim 1 = loga b n→∞ logbn n→∞ logb n n→∞ 26 log nc ∈ O(log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License So, e.g.: Also, since log nc = c ⋅ log n O(logan) = O(logbn) Back to Euclid 27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Back to Euclid Running time is linear in size (in bits) of input, i.e. O(log(m + n)) 27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Back to Euclid Running time is linear in size (in bits) of input, i.e. O(log(m + n)) since the value of m (and n) is at least halved in every two iterations. 27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Back to Euclid Running time is linear in size (in bits) of input, i.e. O(log(m + n)) since the value of m (and n) is at least halved in every two iterations. Why? After two iterations, m becomes m mod n; also 1

Related Posts